Java 集合类学习 Deque 双端队列
什么是双端队列?
双端队列(Double-ended queue)是与队列类似的有序集合。它有一前、一后两端,元素在其中保持自己的位置。与队列不同的是,双端队列对在哪一端添加和移除元素没有任何限制。新元素既可以被添加到前端,也可以被添加到后端。同理,已有的元素也能从任意一端进行移除。某种意义上,双端队列是栈和队列的结合。
Deque 接口
注意:Deque 既可以用作后进先出的栈,也可以用作先进先出的队列。
Deque 接口定义如下:
public interface Deque<E> extends Queue<E> {
// *** Deque methods ***
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);
// *** Queue methods ***
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
// *** Stack methods ***
void push(E e);
E pop();
// *** Collection methods ***
boolean remove(Object o);
boolean contains(Object o);
public int size();
Iterator<E> iterator();
Iterator<E> descendingIterator();
}
双端队列方法
插入
- addFirst 和 offerFirst 在 Deque 实例头部插入元素。
- addLast 和 offerLast 在 Deque 实例尾部插入元素。
当 Deque 实现类为有限容量时,优先使用 offerFirst 和 offerLast,因为 addFirst 在队列满的时候可能会插入失败而抛出异常。
删除
- removeFirst 和 pollFirst 从 Deque 实例头部移除元素。
- removeLast 和 pollLast 从 Deque 实例尾部移除元素。
当 Deque 为空时,pollFirst 和 pollLast 将会返回 null,而 removeFirst 和 removeLast 将会抛出异常。
检索
getFirst 和 peekFirst 获取 Deque 实例的第一个元素,但是不会将元素从 Deque 实例中删除。类似地,getLast 和 peekLast 获取最后一个元素。当 Deque 为空时,getFirst 和 getLast 将会抛出异常,而 peekFirst 和 peekLast 将会返回 null。
除了基本的插入、删除和检索方法外,还有两个预定义的方法:removeFirstOccurence 和 removeLastOccurence。这两个方法见名知意。返回 true 的时候表示元素存在于队列,并且已经被删除。返回 false 时表示元素不存在于队列中,并且队列没有改变。
Deque 接口实现类
Java 集合框架对 Deque 接口有几类实现:数组(Resizable Array)、链表(Linked List)。
ArrayDeque:数组实现
LinkedList:链表实现
LinkedList 内部结构
LinkedList 底层的数据结构是基于双向循环链表的,且头结点中不存放数据,如下:
LinkedList 包含两个重要的成员:header 和 size。
- header 是双向链表的表头,它是双向链表节点所对应的类 Entry 的实例;
- size 是双向链表中节点的个数。
既然是双向链表,那么必定存在一种数据结构——我们可以称之为节点,节点实例保存业务数据,前一个节点的位置信息和后一个节点位置信息,如下图所示:
Entry 中包含成员变量:previous, next, element
- previous 是该节点的上一个节点
- next 是该节点的下一个节点
- element 是该节点所包含的值。
访问性 LinkedList 实际上是通过 双向链表 去实现的。既然是双向链表,那么它的顺序访问会非常高效,而随机访问效率比较低。
LinkedList 是双向链表,但是它也实现了 List 接口,也就是说,它实现了 get(int index)
、remove(int index)
等根据索引值来获取、删除节点的函数。
它增删一个元素会比较方便
public boolean add(E e) {
linkLast(e);
return true;
}
// 因为是双向链表,所以直接更改最后一个元素的指向就行了
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
前面说了 LinkedList 继承自 AbstractSequentialList,AbstractSequentialList 内部优化了对于链表这种 List 随机访问的能力,内部维护一个计数索引值
例如,当程序调用 get(int index)
方法时,首先会比较 Location 和双向链表长度的 1/2
;如果前者大,则从链表头开始向后查找,直到 Location 位置;否则,从链表末尾开始向前查找,直到 Location 位置。(注意,这个不是二分法,它还是遍历实现的)
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
所以每次随机访问都是需要遍历一遍数组,而当访问的元素位于 List 中间,那就是花费最长的时候
双端队列的使用
使用例:
import java.util.Deque;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
Deque<String> deque = new LinkedList<>();
deque.offerLast("A"); // A
deque.offerLast("B"); // A <- B
deque.offerFirst("C"); // C <- A <- B
System.out.println(deque.pollFirst()); // C, 剩下A <- B
System.out.println(deque.pollLast()); // B, 剩下A
System.out.println(deque.pollFirst()); // A
System.out.println(deque.pollFirst()); // null
}
}
如果直接写 deque.offer()
,我们就需要思考,offer()
实际上是 offerLast()
,如果我们明确地写上 offerLast()
,那么不需要思考就能一眼看出这是添加到队尾。因此,使用 Deque,推荐总是明确调用 offerLast()/offerFirst()
或者 pollFirst()/pollLast()
方法。
Deque 是一个接口,它的实现类有 ArrayDeque 和 LinkedList。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
我们发现 LinkedList 真是一个全能选手,它即是 List,又是 Queue,还是 Deque。但是我们在使用的时候,总是用特定的接口来引用它,这是因为持有接口说明代码的抽象层次更高,而且接口本身定义的方法代表了特定的用途。
// 不推荐的写法:
LinkedList<String> d1 = new LinkedList<>();
d1.offerLast("z");
// 推荐的写法:
Deque<String> d2 = new LinkedList<>();
d2.offerLast("z");
Deque 用作 Stack
Deque 数据结构也可以被用作 Stack栈(LIFO),Java 官方也建议开发者使用 Deque 取代旧版 Stack 类。当 Deque 被当作栈使用时,元素都从队头(Head)出入栈。Deque 也定义了栈的基本操作方法。
Stack Method | Equivalent Deque Method |
---|---|
push(e) | addFirst(e) |
pop() | removeFirst() |
peek() | peekFirst() |
表:Deque 与 Stack 方法比较表
import java.util.Deque;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
/* Create a stack of strings based on deque */
Deque<String> aStack = new LinkedList<String>();
/* Push elements to stack */
aStack.push("Java");
aStack.push("Python");
aStack.push("JavaScript");
aStack.push("C/C++");
aStack.push("Golang");
/* Print stack details */
showDeque("Stack", aStack);
/* Pop elements from stack */
while (!aStack.isEmpty()) {
String e = aStack.pop();
System.out.println(e);
}
/* Print stack details */
showDeque("Stack", aStack);
}
public static <T> void showDeque(String name, Deque<T> deque) {
System.out.printf(
"%s(%d): %s" +
System.getProperty("line.separator"),
name, deque.size(), deque.toString()
);
}
}